package baseclass.k_array;

import java.util.Arrays;

/**
 * 给定一个数组arr， 返回所有子数组的累加和中， 最小的累加和
 *
 * @date 2020/3/4 17:50
 */
public class Code03_SubArrayMinSum {
    //方式1：暴力遍历所有子串，然后遍历子串相加，需要时间o(N³)
    public static int getMaxSum1(int[] arr) {
        if (arr == null || arr.length == 0)
            return 0;
        //遍历所有子串
        int sum = 0;
        int res = Integer.MAX_VALUE;
        //当前其实位置为i，则j是从i开始一直到arr.length-1，遍历这中间的所有元素加起来
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                //这里是遍历当前子串的和
                sum = 0;
                for (int index = i; index <= j; index++) {
                    sum += arr[index];
                }
                //更新子串最小和
                res = Math.min(sum, res);
            }
        }
        return res;
    }

    public static int getMaxSum2(int[] arr) {
        if(arr == null || arr.length == 0)return 0;
        /**
         * sum[i] = sum[i-1] + arr[i] ,  sum[i-1] <= 0。前i-1个和小于0，仍要累计起来
         * sum[i] = arr[i] ,    sum[i-1] > 0。前i-1个和已经大于0了，从头开始
         */
        int res = Integer.MAX_VALUE;
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            if(sum > 0) {
                sum = arr[i];
            }else {
                //assert sum <= 0
                sum += arr[i];
            }
            res = Math.min(res,sum);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {-5, 3, -3, 1, -1, 4, -1, 7, -2};
        System.out.println(getMaxSum1(arr));
        System.out.println(getMaxSum2(arr));
        for (int i = 0; i < 100000; i++) {
            arr =  generateRandomArray(10,10);
            if(getMaxSum1(arr) != getMaxSum2(arr)){
                System.out.println(Arrays.toString(arr));
                break;
            }
        }
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        //产生 [0-maxsize]随机长度的数组
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            //随机产生数据
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

}
